package tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TestBinaryTree {
    public TreeNode root;// 根节点

    public TreeNode createTree1() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        a.right = b;
        b.left = c;
        this.root = a;
        return a;
    }

    public TreeNode createTree() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');
//        TreeNode i = new TreeNode('I');
//        TreeNode j = new TreeNode('J');
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        e.right = h;
//        h.left = i;
//        h.right = j;
        this.root = a;
        return a;
    }

    public void preOrder(TreeNode root) { // 前序遍历
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //    public List<Character> preorderTraversal(TreeNode root) { //
////
////        if(root != null) {
////            temp.add(root.val);
////            preorderTraversal(root.left);
////            preorderTraversal(root.right);
////        }
////        return temp;
//        List<Character> temp = new LinkedList<>();
//        if(root == null){
//            return temp;
//        }
//        temp.add(root.val);
//        List<Character> lifeTree = preorderTraversal(root.left);
//        temp.addAll(lifeTree);
//        List<Character> rightTree = preorderTraversal(root.left);
//        temp.addAll(rightTree);
//        return temp;
//    }
    public void middleOrder(TreeNode root) { // 中序遍历
        if (root == null) {
            return;
        }
        middleOrder(root.left);
        System.out.print(root.val + " ");
        middleOrder(root.right);
    }

    public void lastOrder(TreeNode root) { // 后序遍历
        if (root == null) {
            return;
        }
        lastOrder(root.left);
        lastOrder(root.right);
        System.out.print(root.val + " ");
    }

    public int size(TreeNode root) {  // 求树的节点的个数
//        int count = 0;
//        if(root == null){
//            return count;
//        }
//        count++;
//        int leftCount = size(root.left);
//        count += leftCount;
//        int rightCount = size(root.right);
//        count += rightCount;
//        return count;
        if (root == null) {
            return 0;
        }
        int leftSize = size(root.left);
        int rightSize = size(root.right);
        return leftSize + rightSize + 1;
    }

    public int getLeafNodeSize(TreeNode root) { // 叶子结点个数
//        if(root.left == null && root.right == null){
//            return 1;
//        }
//        int leftLeaf = 0,rightLeaf = 0;
//        if(root.left != null) {
//            leftLeaf = getLeafNodeSize(root.left);
//        }
//        if(root.right!=null) {
//            rightLeaf = getLeafNodeSize(root.right);
//        }
//        return leftLeaf + rightLeaf;
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftLeaf = getLeafNodeSize(root.left);
        int rightLeaf = getLeafNodeSize(root.right);
        return leftLeaf + rightLeaf;
    }

    public int nNodeSize(int n, TreeNode root) {  // 求第 n层的节点个数
        if (root == null) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int leftSize = nNodeSize(n - 1, root.left);
        int rightSize = nNodeSize(n - 1, root.right);
        return leftSize + rightSize;
    }

    public int getHeight(TreeNode root) {  // 求树的高度
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public boolean isEntirelyTree(TreeNode root) { // 判断是否为完全二叉树
        if (root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur = queue.poll();
        while (cur != null) {
            queue.offer(root.left);
            queue.offer(root.right);
            cur = queue.poll();
        }
        while (!queue.isEmpty()) {
            if (queue.pop() != null) {
                return false;
            }
        }
        return true;
    }

    public List<Character> preNon_recursion(TreeNode root) { // 前序遍历非递归实现
        Deque<TreeNode> stack = new LinkedList<>();
        List<Character> list = new ArrayList<>();
        TreeNode cur = root;
        while (true) {
            if (cur != null) {
                list.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode temp = stack.pop();
                cur = temp.right;
            }
            if (stack.isEmpty() && cur == null) {
                break;
            }
        }
        return list;
    }

    public List<Character> middleNon_recursion(TreeNode root) { // 中序遍历非递归
        Deque<TreeNode> stack = new LinkedList<>();
        List<Character> list = new ArrayList<>();
        TreeNode cur = root;
        if (root == null) {
            return list;
        }
        while (true) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode temp = stack.pop();
                list.add(temp.val);
                cur = temp.right;
            }
            if (stack.isEmpty() && cur == null) {
                break;
            }
        }
        return list;
    }

    public List<Character> lateNon_recursion(TreeNode root) {  // 后序遍历非递归
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return null;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode temp1 = null;
        while (true) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode temp = stack.peek();
            if (temp.right == null || temp.right == temp1) {
                temp = stack.pop();
                list.add(temp.val);
                temp1 = temp;
            } else {
                cur = temp.right;
            }
            if (stack.isEmpty() && cur == null) {
                break;
            }
        }
        return list;
    }
}
